#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class Solution
{
public:
    string kthDistinct(vector<string> &arr, int k)
    {
        unordered_map<string, int> arrMap;
        for (auto &a : arr)
        {
            arrMap[a]++;
        }
        for (auto &[key, v] : arrMap)
        {
            if (v == 1)
            {
                k--;
            }
            if (!k)
            {
                return key;
            }
        }
        return "";
    }

    string kthDistinct_1(vector<string> &arr, int k)
    {
        // 维护 arr 中每个字符串的频数
        unordered_map<string, int> freq;
        for (const string &s : arr)
        {
            ++freq[s];
        }
        // 遍历 arr 寻找第 k 个独一无二的字符串
        for (const string &s : arr)
        {
            if (freq[s] == 1)
            {
                --k;
                if (!k)
                    return s;
            }
        }
        return "";
    }
};
int main()
{
    Solution s;
    vector<string> arr = {"aaa", "aa", "a"};
    int k = 2;
    cout << s.kthDistinct_1(arr, k) << endl;
    return 0;
}